#include <bits/stdc++.h>


using namespace std;

class Solution{
public:
    int minElement(vector<int> &nums){
        auto get=[&](int x)->int{
            int res=0;
            while(x!=0){
                res=res+x%10;
                x/=10;
            } return res;
        };
        vector<int> res;
        for(auto x: nums) res.push_back(get(x));
        return *min_element(res.begin(), res.end());
    }
};

#define ll long long
class Solution2{
public:
    ll maximumTotalSum(vector<int> &as){
        sort(as.begin(), as.end(), greater<int>()); ll ans=0;
        for(int i=1;i<as.size();i++){
            if(as[i]>=as[i-1]) as[i]=as[i-1]-1;
            if(as[i]<=0) return -1;
        } return accumulate(as.begin(), as.end(), 0LL);
    }
};

class Solution3{
public:
    vector<int> validSuq(string as, string ba){
        int n=as.size(), m=ba.size(), r=m-1;
        vector<int> res(n+1);
        for(int i=n-1;i>=0;i--){
            res[i]=res[i+1];
            if(r>=0 && ba[r]==as[i]) {
                r--;
                res[i]++;
            }
        }
        vector<int> ans; int l=0,ok=1;
        for(int i=0;i<n&&l<m;i++){
            if(as[i]==ba[l]){
                ans.push_back(i);
                l++;
            } else if(ok && res[i+1]>m-l-2){
                ok=0;
                ans.push_back(i);
                l++;
            }
        }
        if(ans.size()!=m) return {}; return ans;
    }
};

class Solution4 {
public:
    template<class T>
    struct ex_KMP{
        T s1, s2;
        vector<int> nxt, ex;
        int n, m;
        ex_KMP(T s1, T s2) : nxt(s2.size()), ex(s1.size()) {
            n = s1.size();
            m = s2.size();
            this -> s1 = s1;
            this -> s2 = s2;
            int a = 0, p = 0;
            nxt[0] = m;
            for(int i = 1; i < m; i++) {
                if (i >= p || i + nxt[i - a] >= p) {
                    if (i >= p) p = i;
                    while (p < m && s2[p] == s2[p - i]) p++;
                    nxt[i] = p - i;
                    a = i;
                } else nxt[i] = nxt[i - a];
            }
            a = 0;
            p = 0;
            for (int i = 0; i < n; i++) {
                if (i >= p || i + nxt[i - a] >= p) {
                    if (i >= p) p = i;
                    while (p < n && p - i < m && s1[p] == s2[p - i]) p++;
                    ex[i] = p - i;
                    a = i;
                } else ex[i] = nxt[i - a];
            }
        }
        int get(int i) {
            return ex[i];
        }
    };

    int minStartingIndex(string s, string pattern) {
        ex_KMP<string> k1(s, pattern);
        reverse(s.begin(), s.end());
        reverse(pattern.begin(), pattern.end());
        ex_KMP<string> k2(s, pattern);
        int ans = -1;
        int n = s.size(), m = pattern.size();
        for (int i = 0; i < n - m + 1; i++) {
            if (k1.get(i) + k2.get(n - i - m) >= m - 1) return i;
        }
        return ans;
    }
};

int main(){
    vector<int> num={1,2,3,4};
    Solution s;cout<<s.minElement(num)<<endl;
    vector<int> nums1={2,3,4,3};
    Solution2 s2;cout<<s2.maximumTotalSum(nums1)<<endl;
    Solution3 s3; vector<int> ans=s3.validSuq("vbcca","abc"); for(auto i: ans) cout<<i<<" ";cout<<endl;
    Solution4 s4;cout<<s4.minStartingIndex("abcdefg","bcdffg")<<endl;
    return 0;
}